package com.topInterview;

/**
 * @Author: huangzhigao
 * @Date: 2022/2/20 16:58
 */
public class Leecode76_subCoverStr {
    public static String minWindow(String s, String t) {
        int[] map = new int[256];
        char[] str = s.toCharArray();
        char[] target = t.toCharArray();
        for (char cha : target) {
            map[cha]++;
        }

        int L = 0;
        int R = 0;
        int all = target.length;
        int minLength = -1;

        int ansl = -1;
        int ansr = -1;

        while (R != str.length) {
            map[str[R]]--;
            if (map[str[R]] >= 0) {
                //有效匹配，因为map大于>0的元素，必然是t中出现的字符
                all--;
            }

            if (all == 0) {
                //收集答案
                while (map[str[L]] < 0) {
                    //不断缩小左侧不会造成匹配不上的字符，寻找出以r结果，能匹配上的最小字符
                    map[str[L++]]++;
                }
                if (minLength == -1 || minLength > R -L + 1) {
                    minLength = R -L + 1;
                    ansl = L;
                    ansr = R;
                }
                //此时让L继续往下划，使之开始又不匹配
                all++;
                map[str[L++]]++;
            }
            R++;
        }


        return minLength == -1 ? "" : s.substring(ansl, ansr + 1);
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s, t));
    }
}
